For many computer process applications, it is necessary to scale input data of lower resolution into output data of higher resolution in order to achieve acceptable, usable, or improved results.
Representative data often presents a low resolution input data set that is a poor replication of the original source. The data presents something much less than a true-life rendering. Many types of source data can benefit by data resolution enhancement: computer image data, digital or analog video data, geographic data measured on a regular grid, vector field data, speech synthesis signals data, and the like.
As to more specific examples in the field of image processing, such as, digital scanning, dot matrix printing, digital camera to video display conversion, digital photography, Internet provider data, JPEG computer image standards, CDROM, magnetic resonance imaging, interframe interpolation for analog video, and the like, the source of the imaging data often provides graphical image data (including bit mapped alphanumeric text images) which is of a relatively low resolution. The term “graphics” as used herein shall be understood to be generic for all forms of imaging. Therefore, output renderings made directly from the source data may be of a low quality.
Moreover, source images, such as, JPEG photographs, Internet files, are often compressed using relatively high data loss compression algorithms to reduce memory storage requirements for the providers. In some cases, decompression algorithms applied when the data is retrieved from memory essentially interpolate the reduced data using simple linear interpolation techniques that lack the precision necessary to reproduce the original image.
For example, in color printing, such as with laser or ink-jet dot matrix hard copy apparatus, resolution enhancement may be necessary to create a print with higher resolution in order to provide a sharper, less blocky, and smoother textured image. In another case, resolution enhancement may be necessary to zoom in and crop a video image before printing, or merely to enhance a particular detail within the original image.
Some prior image scaling techniques provide resolution enhancement through linear filtering approaches. These approaches tend to be less computationally intensive by averaging pixel values across a particular direction. A particular drawback to linear filtering is that sharp edges in the higher resolution image appear blurry and blocky. Previously, the linear filtering approaches were not able to distinguish between sharp edge regions and smooth transition regions to adapt their processing in or around the regions containing sharp edges.
For example, B-spline interpolators, such as image picture element (“pixel”) replication and bilinear interpolation, are well known in the art. The technique of B-spline interpolation specifies an interpolating function which approximates the original image by sampling across a range of the source image data. The interpolating function is defined on a continuous-valued parameter and may be evaluated at arbitrary points. The resulting values comprise the interpolated image pixels. However, a major drawback to B-spline interpolation is the amount of computation needed before recovering the desired output samples, which increases the complexity and cost of B-spline interpolation techniques, especially for higher orders of B-spline interpolation techniques, such as cubic B-spline interpolations. Moreover, B-spline interpolation techniques still suffer from blurring around sharp edges in the higher resolution image.
In particular, both pixel replication and bilinear interpolation perform satisfactorily for interpolating smooth textures. However, these single linear filter approaches tend to average image data across high-contrast boundaries like edges and rapid contrast change zones, causing a blocky or blurry printed result. Thus, these techniques are not especially effective in terms of edge and detail rendition.
More specifically, in pixel replication, the interpolating function is piecewise constant. As such, each output pixel simply takes the value of the closest input pixel. Pixel replication especially tends to produce blocking where the sharp edge appears as stair step edge renderings. Also, pixel replication produces aliasing artifacts where undesirable spurious marks appear.
In bilinear interpolation, the interpolating function is piecewise linear, such that, known data samples are connected with straight lines. As such, each output pixel may be computed as a linear combination of up to four input pixels. Since bilinear interpolation is a simple averaging algorithm, it produces results that can be blurry.
Nonlinear scaling techniques provide an improvement to the linear scaling techniques particularly when dealing with regions with sharp edges. Primarily, the nonlinear scaling techniques locate the regions with sharp edges and treat them differently to avoid blurring cross the edge boundary. In areas not containing sharp edges, the nonlinear scaling techniques use linear scaling techniques, such as, bilinear interpolation. In general, these edge enhancement and smoothing nonlinear techniques find sharp edges in the source data and render them continuous, rather than appearing to have steps, and sharp at the target resolution without blurring the values of pixels which lie on different sides of the edge.
However, these nonlinear scaling techniques often rely on ad hoc characterizations for edge structures which may not reflect the true edge structure. Moreover, some nonlinear scaling techniques, such as those relying on stochastic models for image data, often require iterative optimization which can require excessive computational and/or storage resources.
Two prior approaches include U.S. Pat. No. 6,075,926 (Atkins et al. assigned to the common assignee of the present invention, entitled, “Computerized Method for Improving Data Resolution), and U.S. Pat. No. 6,058,248 (Atkins et al. assigned to the common assignee of the present invention, entitled, “Computerized Method for Improving Data Resolution”). Both approaches use a process to determine a class index for each input pixel, where the class refers to edge sharpness and orientation. However, these previous classification processes require that a feature vector be extracted from the window surrounding the input pixel, and further that distances be calculated between the feature vector and a predetermined set of vectors that represent the different classes requiring additional computational time and resources.
Therefore, prior art methods suffer from either being too computationally complex or too simplistic. For example, linear filtering techniques in the prior art, while less computationally intensive, are disadvantageous because of their inability to maintain sharpness of edges when increasing resolution of an image resulting in blocky or blurry results. In addition, prior art nonlinear filtering techniques, while an improvement to linear filtering, suffer from procedures that are too computationally intensive, such as, iterative operations to distinguish between sharp and smooth edges.